package letterCombinations;

import java.util.*;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 2->(a、b、c)
 * 3->(d、e、f)
 * 4->(g、h、i)
 * 5->(j、k、l)
 * 6->(m、n、o)
 * 7->(p、q、r、s)
 * 8->(t、u、v)
 * 9->(w、x、y、z)
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 * 输入：digits = ""
 * 输出：[]
 *
 * 示例 3：
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 *
 */
public class Solution {
    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) return new ArrayList<>();
        // "234"
        Map<String, List<String>> initMap = new HashMap<>(8);
        initMap.put("2", Arrays.asList("a", "b", "c"));
        initMap.put("3", Arrays.asList("d", "e", "f"));
        initMap.put("4", Arrays.asList("g", "h", "i"));
        initMap.put("5", Arrays.asList("j", "k", "l"));
        initMap.put("6", Arrays.asList("m", "n", "o"));
        initMap.put("7", Arrays.asList("p", "q", "r", "s"));
        initMap.put("8", Arrays.asList("t", "u", "v"));
        initMap.put("9", Arrays.asList("w", "x", "y", "z"));

        Map<String, List<String>> resultMap = new HashMap<>(initMap);
        for (int i = 1; i < digits.toCharArray().length; i++) {
            List<String> characters = initMap.get(digits.charAt(i)+"");
            // 该字符前面的字符
            String preDig = digits.substring(0, i);
            List<String> list = resultMap.get(preDig);
            resultMap.put(preDig + digits.charAt(i), mul(list, characters));
        }
        return resultMap.get(digits);
    }

    private static List<String> mul(List<String> list1, List<String> list2){
        List<String> result = new ArrayList<>();
        for (String item : list1) {
            for (String item1 : list2) {
                result.add(item+item1);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.letterCombinations(""));
    }
}
